Дерево отрезков

A. Дерево отрезков на сумму

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 1024 мегабайта

В этой задаче вам нужно написать обычное дерево отрезков на сумму.

Первая строка содержит два числа $n$ и $m$ $(1 ⩽ n, m ⩽ 100\ 000)$ — размер массива и число операций. Следующая строка содержит $n$ чисел $a_i$ — начальное состояние массива $(0 ⩽ a_i ⩽ 10^9)$. Далее следует описание операций. Описание каждой операции имеет следущий вид:

1 $i$ $v$ — присвоить элементу с индексом $i$ значение $v$ $(0 ⩽ i < n,$ $0 ⩽ v ⩽ 10^9)$.
2 $l$ $r$ — вычислить сумму элементов с индексами от $l$ до $r - 1$ $(0 ⩽ l < r ⩽ n)$.

Выходные данные

Для каждой операции второго типа выведите соответствующую сумму.

Пример

Входные данные

Выходные данные

11
8
14

Решение

B. Число минимумов на отрезке

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 1024 мегабайта

Теперь измените код дерева отрезков, чтобы кроме минимума на отрезке считалось также и число элементов, равных минимуму.

Входные данные

1 $i$ $v$ — присвоить элементу с индексом $i$ значение $v$ $(0 ⩽ i < n,$ $0 ⩽ v ⩽ 10^9)$.
2 $l$ $r$ — найти минимум и число элементов, равных минимуму, среди элементов с индексами от $l$ до $r - 1$ $(0 ⩽ l < r ⩽ n)$.

Выходные данные

Для каждой операции второго типа выведите два числа — минимум на заданном отрезке и число элементов, равных этому минимуму.

Пример

Входные данные

Выходные данные

3 2
2 1
2 3

Решение

C. Отрезок с максимальной суммой

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 1024 мегабайта

В этой задаче вам нужно написать дерево отрезков для нахождения подотрезка с максимальной суммой.

Входные данные

Первая строка содержит два числа $n$ и $m$ $(1 ⩽ n, m ⩽ 100\ 000)$ — размер массива и число операций. Следующая строка содержит $n$ чисел $a_i$ — начальное состояние массива $(-10^9 ⩽ a_i ⩽ 10^9)$. Далее следует описание операций. Описание каждой операции имеет следующий вид: $i$ $v$ — присвоить элементу с индексом $i$ значения $v$ $(0 ⩽ i < n,$ $-10^9 ⩽ v ⩽ 10^9)$.

Выходные данные

Выведите $m + 1$ строку: максимальную сумму чисел на отрезке до всех операций и после каждой операции. Обратите внимание, что этот отрезок может быть пустым (при этом сумма на нем будет равна 0)

Пример

Входные данные

5 2
5 -4 4 3 -5
4 3
3 -1

Выходные данные

8
11
7

Входные данные

4 2
-2 -1 -5 -4
1 3
3 2

Выходные данные

0
3
3

Решение

D. K-я единица

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 1024 мегабайта

В этой задаче вам нужно добавить в дерево отрезков операцию нахождения $k$-й единицы.

Входные данные

Первая строка содержит два числа $n$ и $m$ $(1 ⩽ n, m ⩽ 100\ 000)$ — размер массива и число операций. Следующая строка содержит $n$ чисел $a_i$ — начальное состояние массива $(a_i ∈ {0, 1})$. Далее следует описание операций. Описание каждой операции имеет следущий вид:

1 $i$ — изменить элемент с индексом $i$ на противоположный.
2 $k$ — найти $k$-ю единицу (единицы нумеруются с 0, гарантируется, что в массиве достаточное количество единиц).

Выходные данные

Для каждой операции второго типа выведите индекс соответствующей единицы (все индексы в этой задаче от 0).

Пример

Входные данные

Выходные данные

Решение

E. Первый элемент не меньше X - 2

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 1024 мегабайта

В этой задаче вам нужно добавить в дерево отрезков операцию нахождения по данным $x$ и $l$ минимального индекса $j$, для которого $j ⩾ l$ и $a[j] ⩾ x$.

Входные данные

1 $i$ $v$ — изменить элемент с индексом $i$ на $v$ $(0 ⩽ i < n,$ $0 ⩽ v ⩽ 10^9)$.
2 $x$ $l$ — найти минимальный индекс $j$, для $j ⩾ l$ и $a[j] ⩾ x$ $(0 ⩽ x ⩽ 10^9,$ $0 ⩽ l < n)$. Если такого элемента нет, выведите $-1$. Индексы начинаются с 0.

Выходные данные

Для каждой операции второго типа выведите ответ на запрос.

Пример

Входные данные

Выходные данные

Решение

F. Прибавление и минимум

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 1024 мегабайта

Есть массив из $n$ элементов, изначально заполненный нулями. Вам нужно написать структуру данных, которая обрабатывает два вида запросов:

прибавить к отрезку от $l$ до $r - 1$ число $v$,
узнать минимум на отрезке от $l$ до $r - 1$.

Входные данные

Первая строка содержит два числа $n$ и $m$ $(1 ⩽ n, m ⩽ 100\ 000)$ — размер массива и число операций. Далее следует описание операций. Описание каждой операции имеет следущий вид:

1 $l$ $r$ $v$ — прибавить значение $v$ к отрезку от $l$ до $r - 1$ $(0 ⩽ l < r ⩽ n,$ $0 ⩽ v ⩽ 10^9)$.
2 $l$ $r$ — узнать минимум на отрезке от $l$ до $r - 1$ $(0 ⩽ l < r ⩽ n)$.

Выходные данные

Для каждой операции второго типа выведите соответствующее значение.

Пример

Входные данные

Выходные данные

Решение

G. Присваивание и минимум

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 1024 мегабайта

присвоить всем элементам на отрезке от $l$ до $r - 1$ значение $v$,
узнать минимум на отрезке от $l$ до $r - 1$.

Входные данные

Первая строка содержит два числа $n$ и $m$ $(1 ⩽ n,$ $m ⩽ 100\ 000)$ — размер массива и число операций. Далее следует описание операций. Описание каждой операции имеет следущий вид:

1 $l$ $r$ $v$ — присвоить всем элементам на отрезке от $l$ до $r - 1$ значение $v$ $(0 ⩽ l < r ⩽ n,$ $0 ⩽ v ⩽ 10^9)$.
2 $l$ $r$ — узнать минимум на отрезке от $l$ до $r - 1$ $(0 ⩽ l < r ⩽ n)$.

Выходные данные

Для каждой операции второго типа выведите соответствующее значение.

Пример

Входные данные

Выходные данные

Решение

H. Присваивание, прибавление и сумма

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 1024 мегабайта

Есть массив из $n$ элементов, изначально заполненный нулями. Вам нужно написать структуру данных, которая обрабатывает три вида запросов:

присвоить всем элементам на отрезке от $l$ до $r - 1$ значение $v$,
прибавить ко всем элементам на отрезке от $l$ до $r - 1$ число $v$,
узнать сумму на отрезке от $l$ до $r - 1$.

Входные данные

1 $l$ $r$ $v$ — присвоить всем элементам на отрезке от $l$ до $r - 1$ значение $v$ $(0 ⩽ l < r ⩽ n,$ $0 ⩽ v ⩽ 10^5)$.
2 $l$ $r$ $v$ — прибавить ко всем элементам на отрезке от $l$ до $r - 1$ число $v$ $(0 ⩽ l < r ⩽ n,$ $0 ⩽ v ⩽ 10^5)$.
3 $l$ $r$ — узнать сумму на отрезке от $l$ до $r - 1$ $(0 ⩽ l < r ⩽ n)$.

Выходные данные

Для каждой операции третьего типа выведите соответствующее значение.

Пример

Входные данные

Выходные данные

8
10
4

Решение

I. Криптография

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 1024 мегабайта

Задано $n$ матриц $A_1, A_2, …, A_n$ размера $2 × 2$. Необходимо для нескольких запросов вычислить произведение матриц $A_i, A_{i+1}, …, A_j$. Все вычисления производятся по модулю $r$.

Входные данные

Первая строка входного файла содержит числа $r$ $(1 ⩽ r ⩽ 10\ 000)$, $n$ $(1 ⩽ n ⩽ 200\ 000)$ и $m$ $(1 ⩽ m ⩽ 200\ 000)$. Следующие $n$ блоков по две строки содержащие по два числа в строке — описания матриц. Затем следуют $m$ пар целых чисел от $1$ до $n$, запросы на произведение на отрезке.

Выходные данные

Выведите $m$ блоков по две строки, по два числа в каждой — произведения на отрезках. Разделяйте блоки пустой строкой. Все вычисления производятся по модулю $r$

Пример

Входные данные

Выходные данные

Решение

J. Землетрясения

Ограничение по времени на тест: 1 секунда

Ограничение по памяти на тест: 1024 мегабайта

Город представляет собой последовательность из $n$ клеток, занумерованных числами от 0 до $n - 1$. Изначально все клетки пустые. Далее последовательно происходят $m$ событий одного из двух типов:

в клетке $i$ строится здание с прочностью $h$ (если в этой клетке уже было здание, оно сносится и заменяется на новое),
на отрезке от $l$ до $r - 1$ случается землятресение мощностью $p$, оно разрушает все здания, прочность которых не больше $p$. Ваша задача — для каждого землятресения сказать, сколько зданий оно разрушит.

Входные данные

Первая строка содержит числа $n$ и $m$ — число клеток и число событий $(1 ⩽ n, m ⩽ 10^5)$. Следующие $m$ строк содержат описание событий. Описание каждого события имеет следующий вид:

1 $i$ $h$ — в клетке $i$ строится здание с прочностью $h$ $(0 ⩽ i < n,$ $1 ⩽ h ⩽ 10^9)$.
2 $l$ $r$ $p$ — на отрезке от $l$ до $r - 1$ происходит землятресение с мощностью $p$ $(0 ⩽ l < r ⩽ n,$ $0 ⩽ p ⩽ 10^9)$.

Выходные данные

Для каждого события второго типа выведите, сколько зданий было разрушено.

Пример

Входные данные

Выходные данные

1
1
3

Решение

K. Художник

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 256 мегабайт

Итальянский художник-абстракционист Ф. Мандарино увлекся рисованием одномерных черно-белых картин. Он пытается найти оптимальное местоположение и количество черных участков картины. Для этого он проводит на прямой белые и черные отрезки, и после каждой из таких операций хочет знать количество черных отрезков на получившейся картине и их суммарную длину.

Изначально прямая — белая. Ваша задача — написать программу, которая после каждой из таких операций выводит в выходной файл интересующие художника данные.

Входные данные

В первой строке входного файла содержится общее количество нарисованных отрезков $(1 ⩽ n ⩽ 100\ 000)$. В последующих $n$ строках содержится описание операций. Каждая операция описывается строкой вида $c$ $x$ $l$, где $c$ — цвет отрезка (W для белых отрезков, B для черных), а сам отрезок имеет вид $[x; x+l)$, причем координаты обоих концов — целые числа, не превосходящие по модулю $500\ 000$. Длина задается положительным целым числом.

Выходные данные

После выполнения каждой из операций необходимо вывести в выходной файл на отдельной строке количество черных отрезков на картине и их суммарную длину, разделенные одним пробелом.

Пример

Входные данные

Выходные данные

Решение

L. Окна

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 256 мегабайт

На экране расположены прямоугольные окна, каким-то образом перекрывающиеся (со сторонами, параллельными осям координат). Вам необходимо найти точку, которая покрыта наибольшим числом из них.

Входные данные

В первой строке входного файла записано число окон $n$ $(1 ⩽ n ⩽ 50\ 000)$. Следующие $n$ строк содержат координаты окон $x_{(1, i)}\ y_{(1, i)}\ x_{(2, i)}\ y_{(2, i)}$, где $(x_{(1, i)}, y_{(1, i)})$ — координаты левого верхнего угла $i$-го окна, а $(x_{(2, i)}, y_{(2, i)})$ — правого нижнего (на экране компьютера $y$ растет сверху вниз, а $x$ — слева направо). Все координаты — целые числа, по модулю не превосходящие $2 \cdot 10^5$.

Выходные данные

В первой строке выходного файла выведите максимальное число окон, покрывающих какую-либо из точек в данной конфигурации. Во второй строке выведите два целых числа, разделенные пробелом — координаты точки, покрытой максимальным числом окон. Окна считаются замкнутыми, т.е. покрывающими свои граничные точки.

Пример

Входные данные

2
0 0 3 3
1 1 4 4

Выходные данные

2
1 3

Входные данные

1
0 0 1 1

Выходные данные

1
0 1

Решение

M. Звезды

Ограничение по времени на тест: 2 секунды

Ограничение по памяти на тест: 256 мегабайт

Вася любит наблюдать за звездами. Но следить за всем небом сразу ему тяжело. Поэтому он наблюдает только за частью пространства, ограниченной кубом размером $n × n × n$. Этот куб поделен на маленькие кубики размером $1 × 1 × 1$. Во время его наблюдений могут происходить следующие события:

В каком-то кубике появляются или исчезают несколько звезд.
К нему может заглянуть его друг Петя и поинтересоваться, сколько видно звезд в части пространства, состоящей из нескольких кубиков.

Входные данные

Первая строка входного файла содержит натуральное число $1 ⩽ n ⩽ 128$. Координаты кубиков — целые числа от $0$ до $n - 1$. Далее следуют записи о происходивших событиях по одной в строке. В начале строки записано число $m$. Если $m$ равно:

$1$, то за ним следуют 4 числа — $x, y, z$ $(0 ⩽ x, y, z < N)$ и $k$ $(-20000 ⩽ k ⩽ 20000)$ — координаты кубика и величина, на которую в нем изменилось количество видимых звезд;
$2$, то за ним следуют 6 чисел — $x_1, y_1, z_1, x_2, y_2, z_2$ $(0 ⩽ x_1 ⩽ x_2 < N,$ $0 ⩽ y_1 ⩽ y_2 < N,$ $0 ⩽ z_1 ⩽ z_2 < N)$, которые означают, что Петя попросил подсчитать количество звезд в кубиках $(x, y, z)$ из области: $x_1 ⩽ x ⩽ x_2$, $y_1 ⩽ y ⩽ y_2$, $z_1 ⩽ z ⩽ z_2$;
$3$, то это означает, что Васе надоело наблюдать за звездами и отвечать на вопросы Пети. Эта запись встречается во входном файле только один раз и будет последней.

Количество записей во входном файле не больше $100\ 002$.

Выходные данные

Для каждого Петиного вопроса выведите искомое количество звезд.

Пример

Входные данные

2
2 1 1 1 1 1 1
1 0 0 0 1
1 0 1 0 3
2 0 0 0 0 0 0
2 0 0 0 0 1 0
1 0 1 0 -2
2 0 0 0 1 1 1
3

Выходные данные

Решение

$K$-я порядковая статистика на отрезке

Ограничение по времени на тест: 5 секунд

Ограничение по памяти на тест: 512 мегабайт

Дан массив из $N$ неотрицательных чисел, строго меньших $10^9$. Вам необходимо ответить на несколько запросов о величине $k$-й порядковой статистики на отрезке $[l, r]$.

Входные данные

Первая строка содержит число $N$ $(1 ⩽ N ⩽ 450\ 000)$ — размер массива.

Вторая строка может быть использована для генерации $a_i$ — начальных значений элементов массива. Она содержит три числа $a_1$, $l$ и $m$ $(0 ⩽ a_1, l, m < 10^9)$; для $i$ от $2$ до $N$

$$a_i = (a_{i - 1} \cdot l + m) \bmod 10^9$$

В частности, $0 ⩽ a_i < 10^9$.

Третья строка содержит одно целое число $B$ $(1 ⩽ B ⩽ 1000)$ — количество групп запросов.

Следующие $B$ строк описывают одну группу запросов. Каждая группа запросов описывается 10 числами. Первое число $G$ обозначает количество запросов в группе. Далее следуют числа $x_1$, $l_x$ и $m_x$, затем $y_1$, $l_y$ и $m_y$, затем, $k_1$, $l_k$ и $m_k$ $(1 ⩽ x_1 ⩽ y_1 ⩽ N,$ $1 ⩽ k_1 ⩽ y_1 - x_1 + 1,$ $0 ⩽ l_x, m_x, l_y, m_y, l_k, m_k < 10^9)$. Эти числа используются для генерации вспомогательных последовательностей $x_g$ и $y_g$, а также параметров запросов $i_g$, $j_g$ и $k_g$ $(1 ⩽ g ⩽ G)$

$$ \begin{align*} x_g &= ((i_{g-1} \cdot l_x + m_x) \bmod N) + 1, & 2 ⩽ g ⩽ G \\ y_g &= ((j_{g-1} \cdot l_y + m_y) \bmod N) + 1, & 2 ⩽ g ⩽ G \\ i_g &= \min(x_g, y_g), & 1 ⩽ g ⩽ G \\ j_g &= \max(x_g, y_g), & 1 ⩽ g ⩽ G \\ k_g &= (((k_{g-1} - 1) \cdot l_k + m_k) \bmod (j_g - i_g + 1)) + 1 & 2 ⩽ g ⩽ G \end{align*} $$

Сгенерированные последовательности описывают запросы, $g$-й запрос состоит в поиске $k_g$-го по величине числа среди элементов отрезка $[i_g, j_g]$.

Суммарное количество запросов не превосходит $600\ 000$.

Выходные данные

Выведите единственное число — сумму ответов на запросы.

Пример

Входные данные

5
1 1 1
5
1
1 0 0 3 0 0 2 0 0
1
2 0 0 5 0 0 3 0 0
1
1 0 0 5 0 0 5 0 0
1
3 0 0 3 0 0 1 0 0
1
1 0 0 4 0 0 1 0 0

Выходные данные

Алгоритмы и Структуры данных

Дерево отрезков